#include<unordered_map>
#include<vector>
using namespace std;

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        //知识点①同余定理 （a-b）%k == 0 ，则a%k = b%k
        //知识点②C++中 负数%正数 结果为负数，需要+正数修正 。为了统一正负数（a%b + b）%b
        unordered_map<int,int> hash; //hash表中放修正的余数
        int n = nums.size() ,sum = 0 ,ret = 0;
        hash[0] = 1;  //当sum = k时，就少算了一个
        for(int i = 0 ; i < n ; i++ ){
            sum += nums[i];
            if(hash.count((sum%k + k)%k)) ret += hash[(sum%k + k)%k];
            hash[(sum%k + k)%k]++;
        }
         return ret;
    }
};